//双向循环链表库
#include <iostream>
#include <cstdlib>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

typedef int Status;
typedef int ElemType;

typedef struct LNode{
	ElemType data;
	struct LNode *next, *pre;
	int freq;
}LNode;

class DbcList
{
private:
	LNode *head;
public:
	DbcList();
	Status InitList();
	Status DestroyList();
	Status ClearList();
	Status ListEmpty();
	int ListLength();
	ElemType GetElem(int i);
	int LocateElem(ElemType e, bool (*)(ElemType, ElemType));
	ElemType PriorElem(ElemType cur_e);
	ElemType NextElem(ElemType cur_e);
	Status ListInsert(ElemType e, int i);
	ElemType ListDelete(int i);
};

DbcList::DbcList()
{
	Status st;
	st = InitList();
	if(st != 1)
		exit(0);
}

Status DbcList::InitList()
{
	this->head = (LNode *)malloc(sizeof(LNode));
	this->head->next = this->head->pre = this->head;
	return OK;
}

Status DbcList::DestroyList()
{
	LNode *p = this->head->next, *q;
	while(p!=this->head)
	{
		q = p;
		p = p -> next;
		std::cout << "free " << q->data << std::endl;
		free(q);
	}
	this->head->next = this->head->pre = this->head;
	return OK;
}

Status DbcList::ClearList()
{
	return this->DestroyList();
}

Status DbcList::ListEmpty()
{
	return (this->head->next == this->head);
}

int DbcList::ListLength()
{
	LNode *p = this->head->next;
	int length = 0;
	while(p != this->head)
	{
		p = p->next;
		length++;
	}
	return length;
}

int DbcList::LocateElem(ElemType e, bool (*func)(ElemType, ElemType))
{
	LNode *p = this->head->next;
	int count = 1;
	while(p != this->head)
	{
		if((*func)(p->data, e))
			break;
		p = p->next;
		count++;
	}
	if(p == this->head)
		return 0;
	else
	{
		p->freq++;
		while((p->freq > p->pre->freq) && (p != this->head->next))
		{
			LNode *q = p->pre;
			q->pre->next = p;
			p->next->pre = q;
			p->pre = q->pre;
			q->next = p->next;
			p->next = q;
			q->pre = p;
		}
		return count;
	}	
}

int DbcList::PriorElem(ElemType cur_e)
{
	LNode *p = this->head->next;
	if(p->data == cur_e)
		return p->pre->pre->data;
	while(p != this->head)
	{
		if(p->data == cur_e)
			return p->pre->data;
		p = p->next;
	}
	if(p->next == this->head)
		exit(ERROR);
	return ERROR;
}

ElemType DbcList::NextElem(ElemType cur_e)
{
	LNode *p = this->head->next;
	while(p->next != this->head)
	{
		if(p->data == cur_e)
			return p->next->data;
		p = p->next;
	}
	if(p->data == cur_e)
		return p->next->next->data;
	else
		exit(ERROR);
}

ElemType DbcList::GetElem(int i)
{
	LNode *p = this->head->next;
	int j;
	for(j = 1; (p != this->head) && j < i; j++)
		p = p->next;
	if((p == this->head) || j>i)
		return ERROR;
	return p->data;
}

Status DbcList::ListInsert(ElemType e, int i = -127)
{
	if(i == -127)
		i = this->ListLength() + 1;
	LNode *p = this->head, *s;
	int j;
	for(j = 0; (p->next != this->head) && j < i-1; j++)
		p = p->next;
	if(j > i-1)
		return ERROR;
	s = (LNode *)malloc(sizeof(LNode));
	s->data = e;
	s->freq = 0;
	s->next = p->next;
	p->next = s;
	s->pre = p;
	s->next->pre = s;
	return OK;
}

ElemType DbcList::ListDelete(int i)
{
	LNode *p = (this->head), *q;
	ElemType t;
	int j;
	for(j = 0; (p->next != this->head) && j < i-1; j++)
		p = p->next;
	if((p->next == this->head) || j > i-1)
		exit(ERROR);
	q = p->next;
	p->next = q->next;
	q->next->pre = p;
	t = q->data;
	free(q);
	return t;
}